package schoolrecruiting.algorithm;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 2017年9月7日
 */

/**
 * @author Alex
 *
 */
public class QuickSortAndHeapSort {
	public static void main(String[] args) {
		String str = "9,8,7,6,5,4,3,2,1";
		List<Integer> list = Arrays.asList(str.split(",")).stream().map(x->Integer.parseInt(x)).collect(Collectors.toList());
		int arr[]	= new int [list.size()];
		for(int i=0;i<list.size();i++){
			arr[i]= list.get(i);
		}
		

		//quickSort(arr, 0, arr.length-1);
		heapSort(arr);
		System.out.println(Arrays.toString(arr));
	}
	//从小到大排序要建立大根堆
	public static void heapSort(int arr[]){
		for(int i =arr.length-1;i>=0;i--){
			heapInsert(arr, i);
		}
		for(int i = arr.length-1;i>0;i--){
			swap(arr,0,i);
			heapify(arr, i-1);
		}
	}
	public static  void heapInsert(int arr[],int i){
		int parent = 0;
		while(i>0){
			parent = i/2;
			if(arr[parent]<arr[i]){
				swap(arr,parent,i);
			}else{
				break;
			}
			i = parent;
		}
	}
	
	public static void heapify(int arr[],int end){
		int parent = 0;
		int child = 0;
		while(parent*2+1<end){
			child = parent *2+1;
			//找到比较小的
			if(child<end && arr[child]<arr[child+1]){
				child++;
			}
			if(arr[parent]<arr[child]){
				swap(arr,parent,child);
			}
			parent = child;
		}
	}
	
	public static void quickSort(int arr[],int left,int right){
		if(left>=right)return;
		int mid = partation(arr, left, right);
		quickSort(arr,left,mid-1);
		quickSort(arr,mid+1,right);
		
	}
	public static int partation(int arr[],int left,int right){
		int temp = arr[left];
		while(left<right){
			while(right>left && arr[right]>temp){
				right--;
			}
			if(left<right)
				arr[left++] = arr[right];
			while(right>left && arr[left]<temp){
				left ++ ;
			}
			if(left<right)
				arr[right--]=arr[left];
			
		}
		arr[left] = temp;
		return left;
		
	}
	public static void swap(int arr[],int left,int right){
		int temp = arr[left];
		arr[left] = arr[right];
		arr[right] = temp;
	}
	
}
